1. Field of the Invention
The present invention relates to video images, and more particularly to anti-aliased images provided by a memory efficient system and method.
2. Description of the Related Art
A common operation in the field of computer graphics is the creation of an image based on a representation of the boundaries of numerous 2 dimensional (2d) or 3 dimensional (3d) objects. An image is typically defined by a rectangular array of picture elements (pixels), either in a file, a data structure in the memory of a computer, or a set of rows and columns on a display device or printer. Numerical values associated with each pixel define the color assigned to the corresponding row and column of the image. The numerical values associated with each pixel in an image are determined by establishing which pixels are required to represent each member of a set of 2d or 3d drawing primitives such as vectors, triangles, or polygons. The process of determining the addresses (rows and columns) and numerical values (such as colors) of the pixels associated with a drawing primitive is called rasterizing the primitive.
The set of drawing primitives used to create an image is called a scene or a model. The process of generating an image for a particular scene or model is called rendering the scene or model. The process of rendering a scene or model is accomplished by rasterizing each of the drawing primitives in the scene or model.
Referring to FIG. 1, an apparatus 10 for creating such an image is shown. This includes a memory 12 for storing a boundary representation of a model or scene, a rendering unit 14, an image buffer 16, and a frame buffer 18. The rendering unit 14 includes one or more processors capable of determining the addresses and color values of all pixels associated with each component of the scene or model. The image buffer 16 is a memory with a capacity of at least mxc3x97nxc3x97p bytes, where m is a number of rows in the generated image, n is the number of columns, and p is the number of bytes required to represent each pixel. The frame buffer 18 may be a special memory associated with video digital-to-analog converters (DACs) which produce a visible representation of the image on a cathode ray tube (CRT). In some cases, the frame buffer 18 may be a data file or other data structure. In some cases, the image buffer 16 and frame buffer 18 may be the same physical memory.
Referring to FIG. 2A, when a primitive such as a triangle 20 is rasterized, there are typically a number of pixels 22 on the interior of the triangle which are completely covered by the triangle. Other pixels 24 located on the boundary of the primitive, however, may be only partly covered by the primitive.
In the simplest case, the process of rasterizing a drawing primitive associates pixels with the primitive on an all or nothing basis. For example, if the center of a particular pixel lies within the area of a particular drawing primitive, then the color of that pixel is determined exclusively by that primitive, and other drawing primitives, which may also partially cover the same pixel, are ignored. The result of associating pixels with drawing primitives on an all or nothing basis results in jagged lines along the boundary of a primitive, as shown in FIG. 2B. These jagged boundaries in an image are an undesirable artifact known as aliasing. Techniques for avoiding these artifacts are known as anti-aliasing techniques.
The problem of aliasing may be diminished by super-sampling in which the color of a pixel is determined by a number of points within the area of the pixel instead of representing the pixel by its center. This could be accomplished by using conventional rendering and rasterization techniques to generate a super-image as shown in FIGS. 3A and 3B. Instead of generating an image with m rows and n columns, an image ixc3x97m rows and jxc3x97n columns is generated, where i and j are the super-sampling factors. After the super-image has been completed, each ixc3x97j block of pixels in the super-image is averaged to determine one pixel in the final mxc3x97n anti-aliased image. The color of each pixel in the resulting image reflects the portions of the pixel covered by each drawing primitive, as shown in FIG. 3C.
Referring to FIG. 4, an apparatus 40 required to create an anti-aliased image with the super-image method is shown. In addition to the components of the conventional apparatus shown in FIG. 1, this apparatus has a super-image buffer 42 and an image reduction unit 44. The image reduction unit 44 determines one pixel in the image buffer 16 based on the average value for each ixc3x97j block of pixels in the super-image buffer 42.
The principal problem with the super-image technique is the massive amount of memory required to hold the super-image. A conventional image with a resolution of 600 rows, 800 columns, and 3 bytes per pixel requires nearly 1.5 Mbytes. Super sampling this with factors of i=j=4 would require 16 times as much memory, or roughly 24 Mbytes. If i=j=16, then 256xc3x971.5 Mbytes of memory would be required. In order to implement this in hardware, it would be necessary to provide sufficient real.memory to support the worst case. This would either impose a low upper limit to the super sampling factors, or require providing massive amounts of memory which would be rarely used.
Referring to FIG. 5, an alternative apparatus 50 for generating an anti-aliased image is the use of an accumulation buffer 52. In this case, a conventional mxc3x97n image buffer with e.g., 8-bits for each color value is supplemented with a second mxn buffer having 16-bits for each color buffer.
The accumulation buffer 52 is initially cleared to all zeroes. Then the entire scene is rendered into the first buffer ixc3x97j times, shifting the entire image by multiples of (1/i) rows and (1/j) columns each time. In effect, each rendering pass determines the pixel values determined by every ith row and every jth column of the super-image.
After each rendering pass, the contents of the image buffer 16 are added (block 56) to the contents the accumulation buffer 52. After completing all ixc3x97j passes, each color value in the accumulation buffer 52 is divided (block 58) by ixc3x97j, truncated to an 8-bit integer, and copied back to the image buffer 16. This allows an image to be sampled with up to 256 samples per pixel using only a fixed modest amount of memory beyond that required by the original image buffer 16. One drawback of this is that the entire image must be rendered many times resulting in a severe performance penalty.
The xe2x80x9caccumulation bufferxe2x80x9d method may be summarized as follows:
step b1. Create a digital model of the object(s) or scenery to be rendered.
step b2. Decide on the resolution of the image to be generated by the rendering process (for example, this may be 640xc3x97480, 1280xc3x971024, etc.).
step b3. Traverse the digital model many times. Clipping boundaries are shifted by a fraction of a pixel on each traversal, and each traversal produces a complete image at the full resolution. For example, the model may be traversed 16 times corresponding to shifting the horizontal and vertical clipping boundaries by (xe2x88x92xe2x85x9c, xe2x88x92xe2x85x9, +xe2x85x9, and +xe2x85x9c) pixel.
step b4. On each traversal, each element of the model is processed. That is, the geometry processing is performed and then the results of the geometry processing are immediately passed on to the rasterization processing. This is fully compatible with standard hardware accelerators for 3d graphics.
step b5. The image created in step b4 is added into a special buffer called an xe2x80x9caccumulation bufferxe2x80x9d. An accumulation buffer is similar to an ordinary image buffer, except that the accumulation buffer has 16 bits for each component (r, g, b, and possibly alpha) of each pixel. Each of these components is also called a xe2x80x9csamplexe2x80x9d. The accumulation buffer is not compatible with standard image buffers because it requires 16-bits per sample
step b6. After completing the final traversal, the final image is calculated by dividing each 16-bit component of the accumulation buffer by the number of traversals. The results are stored in a standard image buffer.
Another technique has been implemented by Pixar(trademark) Corp. and forms a major part of their Photorealistic Renderman product. The Pixar(trademark) algorithm divides the work of the rendering unit into two stages, a transformation and clipping stage, and a rasterization stage. The output image is divided into many small blocks. The scene or model is passed to the first stage of the rendering unit only once. Each drawing primitive is transformed and assigned to one or more buckets based on the screen blocks touched by the primitive. After the last element of a scene of model has been processed by the first stage of the rendering unit, the second stage of the rendering unit is used to process each of the buckets created by the first stage. The contents of each bucket are processed with a super-image technique applied to a small part of the complete image. The resulting super-image is reduced to a small image which forms one block in the final anti-aliased image.
One drawback to the Pixar(trademark) algorithm is the need to store a copy of the scene or model between the two stages of the rendering process. The amount of storage needed for this copy of the model cannot be bounded and can be very large for complex models.
Pixar(trademark) uses a rendering algorithm that they call xe2x80x9cREYESxe2x80x9d (Render Everything You Ever Saw). This is incorporated in their product called xe2x80x9cPhotoRealistic RenderManxe2x80x9d. This algorithm is summarized below. Before the Pixar(trademark) algorithm is examined, first consider the xe2x80x9cstandardxe2x80x9d 3d rendering algorithm for reference. The xe2x80x9cstandardxe2x80x9d 3d rendering algorithm may be summarized as:
step s1. Create a digital model of the object(s) or scenery to be rendered. This is a collection of geometrical primitives, material properties, light sources, transformation matrices, etc. which define the properties of the object(s) or scenery.
step s2. Decide on the resolution of the image to be generated by the rendering process (for example, this may be 640xc3x97480, 1280xc3x971024, etc.).
step s3. The digital model is xe2x80x9ctraversedxe2x80x9d, meaning that each element is selected and processed in sequence.
step s4. The processing of each geometric element consists of two stages: xe2x80x9cgeometric processingxe2x80x9d, and rasterizationxe2x80x9d. Both stages are performed in turn for each element of the digital model. That is, for each element, the geometric processing is performed. The results of the geometric processing of this element are then immediately used as input for the rasterization process for the same element. The results of the rasterization process are used to update the image defined in step s2. The results of the geometric processing are discarded after being used as input to the rasterization process.
Note that the xe2x80x9cgeometricxe2x80x9d processing includes transformations, lighting, perspective projection, and clipping the results to the xe2x80x9cviewing frustumxe2x80x9d defined by the view direction and field of view chosen for this image.
The xe2x80x9crasterizationxe2x80x9d processing includes identifying a set of individual pixels associated with a given geometric element in the target image, along with a color value and possibly a transparency value for each of these pixels.
One advantage of the standard algorithm is that it is not necessary to save the intermediate results determined by the geometry processing. These values are fed directly to the rasterization step and then discarded.
The Pixar(trademark) algorithm may be summarized as:
step p1. Create a digital model of the object(s) or scenery to be rendered. This is the same as in step s1.
step p2. Decide on the resolution of the image to be generated by the rendering process (for example, this may be 640xc3x97480, 1280xc3x971024, etc.). Same as step s2.
step p3. Divide the image defined in step p2 into a large number of small squares. These are typically assigned a size of 32xc3x9732, but these could be larger or smaller. A data structure called a xe2x80x9cbucketxe2x80x9d is created for each of the blocks comprising the complete image. (This is a new step not found in the standard algorithm)
step p4. The digital model is xe2x80x9ctraversedxe2x80x9d, meaning that each element is selected and processed in sequence. This is equivalent to step s3.
step p5. Perform the geometry processing for each element of the digital model encountered in step p4. The results of this process are used to determine which bucket(s) is/are affected by each element of the digital model. Each affected bucket is updated to reflect the results of the geometry processing. The geometry processing performed in this step is equivalent to the geometry processing performed in step s4 of the standard algorithm. No rasterization processing is performed in step p5. Each element is expected to affect only a few buckets.
step p6. After completing the traversal of the digital model, each of the buckets is examined to determine which elements of the digital model affect each block of image pixels. In most cases, only a few elements of the complete model are expected to be associated with each bucket. These may be sorted by depth and rasterized to determine the colors of each pixel in the small block of pixels associated with each bucket.
step p7. Each block processed in step p6 block may optionally (and typically) be rasterized at a resolution greater than the size of the block defined in step p3. For example, if each block has the size of 32xc3x9732, then it may be rasterized at a resolution such as 128xc3x97128. The resulting 128xc3x97128 image is then reduced to 32xc3x9732 by averaging blocks of pixels within the 128xc3x97128 image. This produces an anti-aliased image.
step p8. The results of rasterizing each bucket (i.e., a block of pixels) are copied into the corresponding portion of the final image. The final image is completed when the last bucket is processed.
Unlike the standard algorithm, this algorithm requires saving all of the intermediate results of the geometry processing. These results are stored in the array of buckets defined in step p3. This array of buckets may require a large amount of space. This storage requirement is a significant disadvantage. On the other hand, each of the buckets may be processed independently, making this very amenable to parallel processing.
The Pixar(trademark) algorithm is incompatible with typical hardware accelerators for 3d graphics because devices do not allow the results of the geometry processing to be captured and saved into any kind of persistent data storage. These devices assume and require the results of the geometry processing to be passed immediately and directly to the rasterization stage as seen in the standard algorithm.
Therefore, a need exists for a system and method which utilize memory more efficiently for creating and rendering anti-aliased images.
In accordance with the present invention, a program storage device readable by-machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating anti-aliased images and/or a method for creating anti-aliased images includes the steps of providing a subject to be rendered, defining an output resolution of a complete image to be generated by rendering the subject, dividing the complete image into a number of image portions, the number of image portions being determined by an anti-aliasing quality, each image portion having a number of pixels determined by the output resolution of the complete image and the number of image portions, processing the complete image by traversing the subject multiple times to create an intermediate image for each image portion, the intermediate image having a greater number of pixels than the image portion, determining each pixel within the image portion by averaging over blocks of pixels in the intermediate image and combining the image portions to generate the complete anti-aliased image with the output resolution.
In other methods which may be implemented with a program storage device, the step of processing may include the steps of performing geometric processing and immediately passing results of the geometric processing to rasterization processing. The step of processing may include the step of adjusting clipping boundaries on each traversal to select blocks of pixels to be processed. The step of processing the image by traversing may include the step of traversing the subject a number of times equal to a predetermined sub-sampling for each pixel determined by the anti-aliasing quality. The subject may include a digital model of one of objects and scenery to be rendered. The step of reproducing the image portions to produce a final anti-aliased image may include the step of generating an anti-aliased image with resolution of m rows and n columns based on rendering the subject to be rendered ixc3x97j successive times in which each successive rendering is defined by a contiguous mxc3x97n block within the image having ixc3x97m rows and jxc3x97n columns.
A system for creating anti-aliased images includes a memory storage device for storing a boundary representation of an image. A rendering unit is coupled to the memory storage device for determining addresses and color values of all pixels associated the image. A first image buffer is coupled to the rendering unit to receive results from a multiplicity of rendering passes for blocks of ixc3x97j pixels, the first image buffer including a memory with a capacity of at least mxc3x97nxc3x97p bytes, where m is a number of rows in the image, n is the number of columns in the image, and p is the number of bytes needed to represent each pixel. An image reduction unit is coupled to the first image buffer for determining one pixel in the first image buffer based on an average value for each ixc3x97j block of pixels in the first image buffer. A second image buffer is coupled to the image reduction unit having a same size memory capacity as the first image buffer, the second image buffer providing an anti-aliased image after completing the multiplicity of rendering passes.
In alternate embodiments, the memory capacity of the second image buffer is preferably sufficient to produce the anti-aliased image with a same resolution as the image in the second image buffer. The system may further include a frame buffer for producing a visible representation of the anti-aliased image. The frame buffer may include a memory associated with video digital-to-analog converters which produce the visible representation of the image on a display. The frame buffer may have a memory capacity equal to the memory capacity of the second image buffer. The first image buffer may be employed as a frame buffer for producing a visible representation of the anti-aliased image.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.